1753D - The Beach - CodeForces Solution

// becoder Submission #undefined @ 1706758167204
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN=3e5+5;
int n,m,p,q;
struct node{int to;ll w;};
bool operator <(const node &x,const node &y){return x.w>y.w;}
vector<node> G[MAXN];
ll dis[MAXN];
bool vis[MAXN];
void dij(){
    priority_queue<node> q;
    q.push({0,0});
    memset(dis,0x3f,sizeof(dis));
    dis[0]=0;
    while(!q.empty()){
        int u=q.top().to;q.pop();
        if(vis[u])  continue;
        vis[u]=1;
        for(node t:G[u]){
            int v=t.to;
            if(dis[v]>dis[u]+t.w){
                dis[v]=dis[u]+t.w;
                q.push({v,dis[v]});
            }
        }
    }
}
int dir[8][2]={{0,1},{0,-1},{1,0},{-1,0}};
const ll INF=0x3f3f3f3f3f3f3f3f;
int main(){
    #ifndef ONLINE_JUDGE
        freopen(".in","r",stdin);
        freopen(".out","w",stdout);
    #endif
    scanf("%d%d%d%d\n",&n,&m,&p,&q);
    vector<string> mp(n);
    for(int i=0;i<n;i++)   cin>>mp[i];
    auto get=[&](int x,int y)->int {return x*m+y+1;};
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            
            auto link=[&](int x,int y,int w)->void {
                if(x<0||y<0||x>=n||y>=m)    return;
                G[get(x,y)].push_back({get(i,j),1ll*w});
                // cerr<<get(i,j)<<" "<<get(x,y)<<" "<<w<<endl;
            };

            if(mp[i][j]=='L')   link(i-1,j+1,p),link(i+1,j+1,p),link(i,j+2,q);
            if(mp[i][j]=='R')   link(i-1,j-1,p),link(i+1,j-1,p),link(i,j-2,q);
            if(mp[i][j]=='U')   link(i+1,j-1,p),link(i+1,j+1,p),link(i+2,j,q);
            if(mp[i][j]=='D')   link(i-1,j-1,p),link(i-1,j+1,p),link(i-2,j,q);
            if(mp[i][j]=='.')   G[0].push_back({get(i,j),0});
        }
    }
    dij();
    ll ans=INF;
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            for(int k=0;k<4;k++){
                int di=i+dir[k][0],dj=j+dir[k][1];
                if(di<0||di>=n||dj<0||dj>=m)    continue;
                ans=min(ans,dis[get(i,j)]+dis[get(di,dj)]);
            }
        }
    }
    if(ans==INF)    ans=-1;
    printf("%lld",ans);
    return 0;
}